Pseudo-random number generators are employed worldwide in a number of applications. The most prominent uses are sampling and cryptography. Although the most well-known generators produce apparently random numbers, at some point the numbers form a constant pattern, making them only pseudo-random, or random up to a certain point.
There are several types of pseudo-random number generators that have been accepted by the mathematics community as being valid. Modular mathematics is used to restrict the range of the pseudo-random numbers produced. This disclosure contains examples in which various pseudo-random number generators are evaluated using modulo(10) and modulo(1000). Modular numbers generated at these low order (i.e. 1- and 3-digit numbers) can be analyzed more easily, to thereby facilitate an understanding of the principles underlying the invention.
One known pseudo-random number generator is the Linear Congruential. The formula for the Linear Congruential generator is Xn+1=A*Xn+C [mod 1000]. This formula takes the previous number generated, Xn, multiplies it by a seed A, and adds a constant C.
A second pseudo-random number generator is the Additive Congruential (also known as the Fibonacci or Lagged Fibonacci Number Generator.) The formula for the Additive Congruential generator is Xn+1=Xn-s+Xn-r[mod 1000]. This formula requires two seed keys, S and R. This formula works by adding a number S spaces back to a number R spaces back in the series of numbers generated. Closely related is the Subtractive Congruential, which is essentially the same as the Additive Congruential, except the numbers are subtracted rather than added, as can be seen in the formula Xn+1=Xn-s−Xn-r [mod 1000].
The Simple Shift Register generator has the formula Xn+1=(Xn-1* Cirr) [mod 1000] where Cirr is a constant irrational number, such as pi, 2½, etc. The random numbers are selected from a point in the irrational number (i.e. one or more digits are extracted) and each number is multiplied again by the irrational number to produce a new variation.
The Generalized Feedback Shift Register has the formula of Xn+1=Xnq+Xnr+1 [mod 1000]. Both q and r are constant exponents.
There are other kinds of pseudo-random number generators that are based on physical systems, rather than pure number theory. One example of such is the Tausworth, which is a pseudo-random number generator based on the internal electronic operations of a computer and require real-time active measurement. Another method measures uranium decay and counts electrons as a random measure.
There are many tests which can be devised to test the randomness of a pseudo-random number generator. Some of these tests, which are discussed in detail hereinafter, include mean, median, standard deviation, coefficient of correlation, and slope. However, it is to be noted that there is no true test for randomness that is definitive in pseudo-random number generators. Even processes and numbers thought to be random in nature are now being found in some cases to match the Chaos Theory, which shows some regularity after enough investigation and analysis.
Each of the known pseudo-random generators described above was tested for randomness, using the procedure described at the end of this disclosure. The following tests were applied to the results of each generator:                Repetition: Determining where, i.e. after how many numbers, a pattern began and the period (length before repeating) of that pattern.        Average: Arithmetic average (Mean) of all the numbers output from the generator. In theory, an average should equal the midpoint of the possible range if the numbers are random.        Median: The middle number in the set of data, which, ideally, is the middle number of the range.        Standard Deviation: The amount by which the output varies on average from the mean. If a set were truly random, then the standard deviation should be at the quartile points.        Coefficient of Correlation: This tests for a correlation (sequence) within the number output. If the number were truly random, there would be no correlation and the coefficient of correlation would be zero.        Slope: This is very similar to the coefficient of correlation since, ideally, the slope is zero if there is no relationship between the output numbers.        
Using these particular tests, the randomness of each generator can be determined with some certainty. Although there are many other, more complicated, tests, if a generator fails these tests, it can be concluded that it is not producing random numbers for any extended period. The generators were tested first with a modulo(10) implementation.
The Linear Congruential Rational Generator produced unsatisfactory results on every attempt. All of the generators performed poorly and repeated quickly with a very short period. Although they performed poorly, there is no true test for randomness, and that is proven in this example as the average of the generators was 4.58, the median was 4.5, the standard deviation was 2.08 (where 2.5 is the ideal standard deviation), both the coefficient of correlation and the slope had an average near zero. More particularly, looking at only the averages of these tests, the generators appear to be pretty random. However, looking at the repetition in the outputs, the lack of randomness is immediately apparent.
The Linear Congruential Irrational generator is virtually identical to the Linear Congruential Rational generator in repetition and period. However, the averages of the tests are less convincingly random. This is an even less satisfactory generator.
The Simple Fibonacci generator is better than either of the Congruential generators. However, it too repeated, though with a much longer period than either of the Congruential generators. The tests indicated a fair degree of randomness. The average was 4.67, the median was 4.74, the standard deviation was 2.87, and both the coefficient of correlation and the slope were near zero. Nevertheless, the generator exhibits repetition in its output results.
The Simple Shift Register generator produced the worst results. The generator repeated immediately with the smallest possible period. However, some of the tests appeared to show some randomness, which is deceiving. For example, the average and the median were 2.6. If one looked at the coefficient of correlation, which was 0.4227, and the slope, which was 0.4052, without knowing about the immediate repetition, one might be deceived to think there is some randomness.
The Generalized Feedback Shift Register generator did not repeat immediately. However, the generator would normally fall into a repeating pattern when it hit a particular number, most often zero. The pattern was: “3, 2, 4, 1, 9, 7, 5”. The tests, for the most part, gave the impression that the generator is random, but looking at the data on repetition, it is apparent that the generator is not truly random.
The generally poor results produced by these generators reveal their unreliability. It is possible that these generators might have produced more random output digits had the constants in the formulas been different. However, if the choice of seed number(s) or constant(s) can adversely affect an entire run of generators, these generators are unsatisfactory to begin with. If one has to be careful about choosing constants and seeds, then it is clear that the generator is not reliable and another alternative should be found.
Since the generators, for the most part, appeared to repeat fairly quickly, they were also tested in modulo(1000) to give the generators a chance to run with a higher number of possible output digits. That higher number would also help to test whether the modulo choice (i.e. the range of possible outputs) could affect randomness in comparison to the choice of seeds. To test modulo(1000) with a relatively high statistical confidence, each generator run was taken out to at least the 2276th pseudo-random number.
The Linear Congruential Rational Generator was practically the same in modulo(1000), repeating, on average, at the 97.87, or the 98th number. However, once again, the other tests gave the false impression that the generator is truly random. The fact that the generators repeated around the 98th number indicates that only 10% of the population was exhausted before the generator fell into a repeating pattern.
The Linear Congruential Irrational generator is even worse than the Linear Congruential Rational generator, repeating, on average, after the 49.833, or 50th number. Thus, only 5% of the population was exhausted before the generator fell into a repeating pattern.
The Simple Fibonacci generator is the best of the tested generators, repeating, on average, after the 1058.63, or the 1059th number. This means that, theoretically, all of the numbers in the population were exhausted through one cycle before the generator started to repeat. Nevertheless, the generator still repeated, so its reliability is again limited to shorter runs.
The Simple Shift Register generator was, once again, shown to be a fairly non-random generator, repeating, on average, after the 80.75th number, or the 81st number. Although some of the other tests gave the impression that the generator is random, the generator still repeated at a relatively early point in each run.
The Generalized Feedback Shift Register is second best of the tested generators, repeating, on average, after the 984.40th number, or the 984th number. Most of the statistics for this generator gave the impression that the generator is fairly random; however, it too repeated.